﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.ConstrainedExecution;
using System.Text;
using System.Threading.Tasks;

public class Solution416
{
    public bool CanPartition2(int[] nums)//递归回溯，思路正确，但是会超时
    {

        //
        int sum = 0;
        for (int i = 0; i < nums.Length; i++)
        {
            sum += nums[i];
        }
        if (sum % 2 == 0)//偶数。继续
        {

        }
        else
        {
            //奇数，肯定不可能

            return false;
        }

        int target = sum / 2;
        //寻找子数组，满足和为target

        return GetTarget(nums, 0, target);

    }

    private bool GetTarget(int[] nums, int index, int target)
    {
        if (index == nums.Length)
        {
            return false;
        }


        if (target < 0)//说明数组不应该加入
        {
            return false;
        }
        else if (target == 0)
        {//说明满足条件
            return true;
        }
        else//继续循环
        {
            //这个数加入数组

            bool next = GetTarget(nums, index + 1, target - nums[index]);
            if (next)
            {
                return true;
            }
            else
            {
                return GetTarget(nums, index + 1, target);//这个数不加入数组
            }


        }

    }
    public bool CanPartition3(int[] nums)//动态规划
    {

        //
        int sum = 0;
        int max = 0;
        int len = nums.Length;
        for (int i = 0; i < nums.Length; i++)
        {
            sum += nums[i];
            max = Math.Max(max, nums[i]);
        }
        if (sum % 2 == 0)//偶数。继续
        {

        }
        else
        {
            //奇数，肯定不可能

            return false;
        }

        int target = sum / 2;
        if (max > target)
        {
            //数组肯定分不出两部分
            return false;
        }
        //寻找子数组，满足和为target
        bool[][] dp = new bool[len][];
        //dp数组，遍历整个数组，判断当前数字是否加入sum，j遍历整个target，判断
        for (int i = 0; i < len; i++)
        {
            dp[i] = new bool[target + 1];


        }
        //初始条件，cur从1开始算的，所有初始dp【0】
        //dp【0】，代表选择第一个数nums[0]，只有cursum=这个数的时候才选择
        
        dp[0][0] = true;
        dp[0][nums[0]] = true;
        for (int cur = 1; cur < len; cur++)
        {
            dp[cur][0] = true;

            for (int cursum = 1; cursum <= target; cursum++)//想要cursum=0，不选择就可以了，所有的dp[i][0]=true
            {
                //条件是数组的判断当前数字是否加入sum

                //什么情况加入，什么情况不加入？
                //1，加入，nums[cur] <=cursum。 可以加入，也可以不加入。结果选取前面那个状态为true的 
                //2，不加入 nums[cur] > cursum的时候肯定不在当前回合加入数组，因为这个时候一个数就比总和target大了 


                if (nums[cur] > cursum)
                { //不加入，看之前的数组是否符合条件
                    dp[cur][cursum] = dp[cur - 1][cursum];

                }
                else
                {
                    //加入，看加入之前是否有符合条件的数组

                    dp[cur][cursum] = dp[cur - 1][cursum - nums[cur]] | dp[cur - 1][cursum];
                }




            }

        }
        return dp[len-1][target];
    }


    //上述代码的空间复杂度是 O(n×target)。但是可以发现在计算 dp 的过程中，每一行的 dp 值都只与上一行的 dp 值有关，
    //因此只需要一个一维数组即可将空间复杂度降到 O(target)。此时的转移方程为：

    public bool CanPartition(int[] nums)//动态规划，优化
    {

        //
        int sum = 0;
        int max = 0;
        int len = nums.Length;
        for (int i = 0; i < nums.Length; i++)
        {
            sum += nums[i];
            max = Math.Max(max, nums[i]);
        }
        if (sum % 2 == 0)//偶数。继续
        {

        }
        else
        {
            //奇数，肯定不可能

            return false;
        }

        int target = sum / 2;
        if (max > target)
        {
            //数组肯定分不出两部分
            return false;
        }
        //寻找子数组，满足和为target
        bool[] dp = new bool[target+1];
      
        //初始条件，cur从1开始算的，所有初始dp【0】
        //dp【0】，代表选择第一个数nums[0]，只有cursum=这个数的时候才选择

        dp[0] = true;
        dp[nums[0]] = true;

        for (int cur = 1; cur < len; cur++)
        {
         

            for (int cursum = target; cursum>= nums[cur]; cursum--)//使用倒序是因为，dp[cursum - nums[cur]]使用的上一个cur的，而不是上一个cursum
            {


                //if (nums[cur] > cursum)
                //{ //不加入，看之前的数组是否符合条件
                //    dp[cur][cursum] = dp[cur - 1][cursum];

                //}
                //else
                //{
                //    //加入，看加入之前是否有符合条件的数组

                //    dp[cur][cursum] = dp[cur - 1][cursum - nums[cur]] | dp[cur - 1][cursum];
                //}

                //dp数组二维优化为一维是因为dp[cur]和 dp[cur - 1]有关系，所有直接使用上一个cur的数组
                //if (nums[cur] <= cursum)//必须加入,否则dp越界
                //{
                //    dp[cursum] = dp[cursum - nums[cur]] | dp[cursum];
                //}

                dp[cursum] = dp[cursum - nums[cur]] | dp[cursum];//优化
            }

        }
        return dp[target];
    }

}

class Program416
{

    static void Main416(string[] args)
    {

        //int[] nums = [1, 2, 5];
        int[] nums = [1, 5, 11, 5];
        Solution416 solution = new Solution416();
        bool res = solution.CanPartition(nums);
        Console.WriteLine("是否可以将这个数组分割成两个子集" + res);

    }
}
